% !TEX TS-program = pdflatex
\documentclass[10pt, a4paper]{article}

\usepackage{a4wide}
\usepackage{color}
\usepackage{amsmath,amssymb,epsfig,pstricks,xspace}
\usepackage{german,graphics}
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{graphics, psfrag}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{enumitem} 
\usepackage{url}
\usepackage{array,dcolumn,booktabs}
\usepackage{pdflscape}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{graphicx} 


\usepackage{pifont}

\newcommand{\header}{
  \begin{center}
  \fbox{\parbox{11cm}{
    \begin{center}
      {\Large Lab 5.2 -- Solution\\ \vspace{0.2em}
        {\bf Search Algorithms}\\ \vspace{0.7em} (Winter Term 2014/2015)\\
        \vspace{0.2em} \firstnameone \lastnameone\\
        \vspace{0.2em} \matriculationnumberone\\
        \vspace{0.2em} \firstnametwo \lastnametwo\\
        \vspace{0.2em} \matriculationnumbertwo\\
        \vspace{0.2em} \firstnamethree \lastnamethree\\
        \vspace{0.2em} \matriculationnumberthree
    }
    \end{center}
  }}
  \end{center}
}


%-------------------------------------------------------------------------------
%---------------------------- EDIT FROM HERE -----------------------------------
%-------------------------------------------------------------------------------

\newcommand{\firstnameone}{Jiaqi	}
\newcommand{\lastnameone}{Weng}
\newcommand{\matriculationnumberone}{115131}

\newcommand{\firstnametwo}{Vasilii	}
\newcommand{\lastnametwo}{Ponteleev}
\newcommand{\matriculationnumbertwo}{115151}

\newcommand{\firstnamethree}{Le Do Thai	}
\newcommand{\lastnamethree}{Binh   }
\newcommand{\matriculationnumberthree}{114910}

\begin{document}
\pagestyle{plain}
\header


\textbf{Task 1}\\
Based on the actual implementation.\\
Let h = 0.\\
Then finding most promising solution relies only on the distance from starting node to the current node.  It means that open list could be implemented as a priority queue.\\
When the node is being expanded costs g(n) are calculated in the same manner as in unifrorm cost searh. The only thing, that may differ for now, is revisiting and improving elements from a closed list.\\
Since every $n^{'}$  - successor of node being expanded, encodes a new state (we omitted heuristic and there is no way to go back and improve, we go only deeper), $n^{'}$ will be inserted in the open list. So, we effectively have uniform cost search.
\\\\
\textbf{Task 2}\\\\
in open list, there are at most |V|-1 nodes.\\
g denote all pointer paths from s to the nodes in open list nodes.\\
and for every nodes in open list the number of paths from s is at most in upper bound $O((|v|-1)^2)$\\
so the upper bound of |g| is $O((|v|-1)^3)$\\
\\
\textbf{Task 3}\\
Just took it from the slides [Lemma 30].\\\\
1. Base case. s on OPEN. s is on $P_{s-n}$ and is the only and hence shallowest OPEN node.\\
2. Induction hypothesis. $P_{s-n}$ $\cap$ OPEN $\ne$ $\emptyset$ and $n^{'}$ is shallowest OPEN node on $P_{s-n}$. \\
3. Induction step. A* expands a node $n_e$ or terminates (with solution $n_e$). \\
(a) Let $n_e$ = $n^{'}$ . If $n^{'}$ = n, all nodes on $P_{s-n}$ have been expanded. Otherwise, a successor of $n_e$ is on $P_{s-n}$ and is now the shallowest OPEN node on $P_{s-n}$.\\
(b) Let $n_e$ $\ne$ $n^{'}$ . If a predecessor of n 0 on $P_{s-n}$ is reopened, this node is now the shallowest OPEN node on $P_{s-n}$. Otherwise, $n^{'}$ remains the shallowest OPEN node on $P_{s-n}$.
\\\\
\textbf{Task 4}\\
For a monotonic heuristic there is no need to keep a closed list. It holds,  because nodes in the closed list will not be rediscovered.\\\\
\textbf{Task 7}\\\\
a)\\
for 8-puzzle, there are 9!(362880) kinds of states.\\
b)\\
no, if the number of the inversion tiles is odd, the configuration is unsolvable.\\
c)\\
yes\\
d)\\
h0 is not optimistic\\
h1 is not, for [1,2,3,4,5,6,7,0,8], distance is 1, but cost is 2.\\
h2 is optimistic.\\
e)\\
see python code\\
for s1, number of necessary moves is 181439, number of expend nodes is 125618.\\
for s2, unsolvable, number of expend nodes is 125618, crash of heap\\
f)\\
number of necessary moves and expend nodes decline, but not obviously.\\
because h0 is not optimistic.\\
expended nodes number: 100213 for s1\\
g)\\
number of necessary moves and expend nodes decline obviously.\\
because h1 is optimistic.\\
expended nodes number: 6723 for s1\\
\end{document}
